class Solution {
    private int n;
    private int m;
    private int[] fa;
    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        fa = new int[n*m];
        for(int i=0; i<n*m; i++) fa[i]=i;
        int[] dx = {-1, 0, 0, 1};
        int[] dy = {0, 1, -1, 0};
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]=='0')continue;
                for(int k=0; k<4; k++){
                    int nx = dx[k]+i;
                    int ny = dy[k]+j;
                    if(nx<0||ny<0||nx>=m||ny>=n)continue;
                    else{
                        if(grid[nx][ny]=='1')unionSet(num(nx, ny), num(i, j));
                    }
                }
            }
        }
        int ans = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]=='1'&&find(num(i,j))==num(i,j)) ans++;
            }
        }
        return ans;
    }

    private int find(int x){
        if(x == fa[x])return x;
        return fa[x] = find(fa[x]); 
    }

    private void unionSet(int x, int y){
        x = find(x);
        y = find(y);
        if(x!=y) fa[x] = y;
    }

    private int num(int x, int y){
        return x*n+y;
    }
}
/**
    并查集
 */